package leetcode_1000;

public class MinimumFallingPathSum_931 {
	public static void main(String[] args) {
		MinimumFallingPathSum_931 test=new MinimumFallingPathSum_931();
		System.out.println(test.minFallingPathSum(new int[][] {{1,2,3},{4,5,6}}));
	}
	
	public int minFallingPathSum(int[][] A) {
		int row=A.length,col=A[0].length;
        int dp[][]=new int[row][col];
        for(int i=0;i<col;++i) {//初始化
        	dp[0][i]=A[0][i];
        }
        for(int i=1;i<A.length;++i) {
        	dp[i][0]=Math.min(dp[i-1][0], dp[i-1][1])+A[i][0];
        	dp[i][col-1]=Math.min(dp[i-1][col-1], dp[i-1][col-2])+A[i][col-1];
        	for(int j=1;j<col-1;++j) {
        		dp[i][j]=Math.min(dp[i-1][j], Math.min(dp[i-1][j-1], dp[i-1][j+1]))+A[i][j];
        	}
        }
        int res=Integer.MAX_VALUE;
        for(int i=0;i<col;++i)
        	res=Math.min(res, dp[row-1][i]);
        return res;
    }
	
	public int minFallingPathSum1(int[][] A) {
		int n = A.length;
        if (n == 1)
            return A[0][0];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0)
                    A[i][j] += Math.min(A[i-1][j], A[i-1][j+1]);
                else if (j == n-1)
                    A[i][j] += Math.min(A[i-1][j], A[i-1][j-1]);
                else
                    A[i][j] += Math.min(A[i-1][j], Math.min(A[i-1][j-1], A[i-1][j+1]));
                if (i == n - 1)
                    min = Math.min(min, A[i][j]);
            }
        }
        return min;
    }
}
